package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 通过递归的方式 实现二叉树的 遍历
 *  二叉树递归遍历框架
 *  从栈中 拿出一个节点P ，想办法 搞清楚 节点P子节点是不是被遍历
 *  如果左右两个子树都没有遍历的情况下 对 P  进行操作
 *  这个时候 算作   前序遍历
 *  如果 左子树已经遍历 右子树没有进行遍历这个时候 算作 中序遍历
 *  如果左右子树 都已经遍历这个时候对P 节点进行  操作这个时候算作 后续遍历
 *
 */
public class TravelTreeWiithStack {
    public Stack<TreeNode> stack = new Stack<>();

    /**
     * 通用 二 叉树 遍历 模板
     */
    public void basicTravel(TreeNode root){
        pushLeftBranch(root);
        TreeNode peek = stack.peek();
        /**
         * if (peek 的左子树被遍历完) {
         *             // 中西遍历 位置
         *             // 以P为根节点的树被遍历完 出栈
         *             stack.pop();
         *         }
         *
 *         if (peek 的右子树被遍历完) {
 *             // 后序遍历 位置
 *             // 以P为根节点的树被遍历完 出栈
 *             stack.pop();
 *         }
         */


    }
    /**
     * 通用 二 叉树 遍历 模板
     */
    public void basicTravel_V2(TreeNode root){
        pushLeftBranch(root);
        // 用于指向 上一次遍历 的子树根节点
        TreeNode  visited = new TreeNode(-1);
        while (!stack.isEmpty()) {
            TreeNode peek = stack.peek();
            // p 的左子树被遍历完 但是 p的右子树没有遍历  这时候 有动作算作中序遍历
            if ((peek.left == null || peek.left == visited)
                    && peek.right!=visited) {
                // 中序遍历的位置
                // 遍历p的右子树
                pushLeftBranch(peek.right);
            }
            if (peek.right == null || peek.right == visited) {
                // 后序 遍历的代码位置
                visited = stack.pop();
            }

        }


    }

    private List<Integer> inOrderTravelList = new ArrayList<>();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return  inOrderTravelList;
        }
        pushLeftBranch(root);
        // 用于保存 上次访问的节点
        TreeNode visited = new TreeNode(-1);
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.peek();
            // 左边已经遍历过了
            if ((treeNode.left ==null || treeNode.left ==visited) &&
                        treeNode.right!=visited) {
                inOrderTravelList.add(treeNode.val);
                // 遍历 右子树
                pushLeftBranch(treeNode.right);
            }

            if (treeNode.right == null || treeNode.right == visited) {
                // 后序 遍历的代码位置
                visited = stack.pop();
            }

        }
        return inOrderTravelList;

    }


    private void pushLeftBranch(TreeNode p) {
        while (p != null) {
            // 前序遍历  位置
            stack.push(p);
            p = p.left;
        }
    }
}
